<?php

/**
 * Try to traverse a bst without recursion (normally requires a stack)
 */

require_once 'util.php';

importJS();

$arr = generateRandomArray(1, 99, 7);
$value1 = $arr[3];
$value2 = $arr[5];

var_dump($arr);

$root = null;
foreach( $arr as $value ){
	$root = bst_insert($value, $root);
}

//bt_print_inorder($root);
//bt_draw($root);
bt_draw( $root );

echo "<br/>";

bst_iterative_inorder( $root );

echo "<br/>";

bst_iterative_preorder( $root );

echo "<br/>";

bst_iterative_postorder( $root );

// ------------------------------------------
// Note:
// Previous looking for left child failed
// Do a pop and start looking at the pop node's
// RIGHT CHILD!!!
// ------------------------------------------
function bst_iterative_inorder( $root ){
	if( !$root ){
		return;
	}

	$s = array();
	$cur = $root;
	$done = false;

	while( !$done ){
		
		if( !$cur ){

			if( !count($s) ){
				$done = true;
			}
			else {
				$cur = array_pop( $s );
				echo $cur->value." ";
				$cur = $cur->right;
			}			
		}	
		else {
			array_push( $s, $cur );
			$cur = $cur->left;
		}
	}

	return true;
}

// ------------------------------------------
// Note:
// Quite straight forward...
// ------------------------------------------
function bst_iterative_preorder( $root ){
	if( !$root ){
		return;
	}

	$s = array();
	array_push( $s, $root );

	while( count($s) ){

		$cur = array_pop( $s );
		echo $cur->value." ";
		if( $cur->right ){
			array_push( $s, $cur->right );	
		}
		if( $cur->left ){
			array_push( $s, $cur->left );
		}
	}
}

// ------------------------------------------
// Note:
// Troublesome when using a single stack but
// Apply two stack become simple
// Without recursive the loop can only runs 
// top down. The postorder however is the other
// way around so apply another stack to 'reverse'
// ------------------------------------------
function bst_iterative_postorder( $root ){
	if( !$root ){
		return;
	}

	$s1 = array(); // for first traversing
	$s2 = array(); // for the final display order
	array_push( $s1, $root );

	while( count($s1) ){
		$cur = array_pop( $s1 );
		if( $cur->left ){
			array_push( $s1, $cur->left );
		}
		if( $cur->right ){
			array_push( $s1, $cur->right );
		}		
		array_push( $s2, $cur );	
	}

	while( $node = array_pop( $s2 ) ){
		echo $node->value." ";
	}
}